package com.xhj.joffer.linkedList;
import org.junit.Test;

import java.util.HashMap;
/**
 * @author haijianxia pure_xhj@163.com
 * @Date 2021.09.17
 * @Time 17:49
 */
public class FindFirstCommonNode {
	public static void main(String[] args){
		System.out.println("==========================LinkedListTwo==========================");
		LinkedListNodeTwo commonNode = new LinkedListNodeTwo("commonNode");
		LinkedListNodeTwo root1 = new LinkedListNodeTwo("root1", new LinkedListNodeTwo("root1.2", new LinkedListNodeTwo("root1.3",commonNode)));
		LinkedListNodeTwo root2 = new LinkedListNodeTwo("root2", new LinkedListNodeTwo("root2.2", new LinkedListNodeTwo("root2.3",new LinkedListNodeTwo("root2.4", commonNode))));
    System.out.println(root1.toStringTail());
    System.out.println(root2.toStringTail());

		System.out.println("==========================LinkedListOne==========================");
    LinkedListNodeOne rootOne1=new LinkedListNodeOne("rootOne1");
    LinkedListNodeOne rootOne2=new LinkedListNodeOne("rootOne2");
		LinkedListNodeOne commonNodeOne=new LinkedListNodeOne("commonNodeOne");
		rootOne1.next(new LinkedListNodeOne("ro1.2"))
	    .next(new LinkedListNodeOne("ro1.3"))
	    .next(new LinkedListNodeOne("ro1.4"))
	    .next(commonNodeOne)
			.next(new LinkedListNodeOne("ro1.6"));
		rootOne2
			.next(new LinkedListNodeOne("ro2.2"))
			.next(new LinkedListNodeOne("ro2.3"))
			.next(commonNodeOne)
			.next(new LinkedListNodeOne("ro2.5"))
			.next(new LinkedListNodeOne("ro2.6"));
    System.out.println(rootOne1.toStringTail());
    System.out.println(rootOne2.toStringTail());

    System.out.println("==========================find==========================");
		LinkedListNodeOne commonFind = test01(rootOne1, rootOne2);
    System.out.println("commonFind.toString() = " + commonFind.toString());

    if(null==null){
      System.out.println();
    }

    System.out.println("==========================find by hashMap==========================");
		LinkedListNodeOne commonFind2 = test02(rootOne1, rootOne2);
		System.out.println("commonFind2.toString() = " + commonFind2.toString());

		System.out.println("==========================test for null linked==========================");
		LinkedListNodeOne nodeOne = test02(null, null);
		try {
			System.out.println("nodeOne.toString() = " + nodeOne.toString());
		} catch (Exception e) {
      System.out.println("e.getMessage() = " + e.getMessage());
		}
	}
	
	/** 思路一: 双层for */
	@Test
	public static LinkedListNodeOne test01(LinkedListNodeOne linked1,LinkedListNodeOne linked2) {
		System.out.println("\n=============test01==============");
		System.out.println("思路一: 双层for");
		long time01 = System.currentTimeMillis();
		
		LinkedListNodeOne result = new LinkedListNodeOne("");

    if (linked1 == null || linked2==null) {
	    result=null;
    }

		LinkedListNodeOne linked1Now = linked1;
		boolean innerMakeOuterBreak = false;
		do{
			if (linked1 == null) {
				break;
			}
			LinkedListNodeOne linked2Now = linked2;
			do{
				if (linked2 == null) {
					break;
				}
				if(linked1Now==linked2Now){
					result=linked1Now;
					innerMakeOuterBreak = true; break;
				}
				linked2Now=linked2Now.getNext();

			}while(linked2Now!=null);

			if (innerMakeOuterBreak == true) {
				innerMakeOuterBreak = false; break;
			}
			linked1Now=linked1Now.getNext();

		}while(linked1Now!=null);
				 
		long time0101  = System.currentTimeMillis() - time01;
		System.out.println("test01 耗时 =  " + time0101  + "ms");
		System.out.println("=================================");
	
		return result;
	}
	/** 思路二: HashMap */
	@Test
	public static LinkedListNodeOne test02(LinkedListNodeOne linked1, LinkedListNodeOne linked2) {
		System.out.println("\n=============test02==============");
		System.out.println("思路二: HashMap");
		long time02 = System.currentTimeMillis();

		LinkedListNodeOne result =new LinkedListNodeOne("");
		if (linked1 == null || linked2==null) {
			result=null;
		}

		HashMap<LinkedListNodeOne, LinkedListNodeOne> hashMap = new HashMap<>();
		LinkedListNodeOne linked1Now = linked1;
		do{
		  if (linked1Now == null) {
			  break;
		  }
			hashMap.put(linked1Now,linked1Now);
		  linked1Now=linked1Now.getNext();
		}while(linked1Now!=null);

		LinkedListNodeOne linked2Now = linked2;
		do{
			if (linked2Now == null) {
				break;
			}
      if (hashMap.containsKey(linked2Now)) {
        result=hashMap.get(linked2Now);break;
      }
			linked2Now=linked2Now.getNext();
		}while(linked2Now!=null);

		long time0202  = System.currentTimeMillis() - time02;
		System.out.println("test02 耗时 =  " + time0202  + "ms");
		System.out.println("=================================");

		return result;
	}
	/** 思路二: HashMap */
	@Test
	public static ListNode test022(ListNode headA, ListNode headB) {
		System.out.println("\n=============test02==============");
		System.out.println("思路二: HashMap");
		long time02 = System.currentTimeMillis();

		ListNode result =null;
		if (headA == null || headB==null) {
			result=null;
		}

		HashMap<ListNode, ListNode> hashMap = new HashMap<>();
		ListNode head1Now = headA;
		do{
		  if (head1Now == null) {
			  break;
		  }
			hashMap.put(head1Now,head1Now);
		  head1Now=head1Now.next;
		}while(head1Now!=null);

		ListNode linked2Now = headB;
		do{
			if (linked2Now == null) {
				break;
			}
      if (hashMap.containsKey(linked2Now)) {
        result=hashMap.get(linked2Now);break;
      }
			linked2Now=linked2Now.next;
		}while(linked2Now!=null);

		long time0202  = System.currentTimeMillis() - time02;
		System.out.println("test02 耗时 =  " + time0202  + "ms");
		System.out.println("=================================");

		return result;
	}
}
